Convex Optimization: Beyond Hard Constraints: The Lagrangian Framework

In the standard world of optimization, a constraint is a binary wall: either you are in, or you are out. But in complex systems, these "hard" constraints can be mathematically rigid. The Lagrangian framework provides the scaffolding to move beyond this, transforming constraints into "augmented" objective functions that incorporate violations as weighted penalties. This isn't just a trick; it's the foundation for quantifying the "cost" of constraints through Lagrange multipliers.

1. From Hard Constraints to Soft Penalties

Consider a standard problem: minimize $f_0(x)$ subject to $f_i(x) \le 0$ and $h_i(x) = 0$. A "hard" constraint is equivalent to an indicator function:

$$I_-(u) = \begin{cases} 0 & u \leq 0 \\ \infty & u > 0 \end{cases}$$

The Lagrangian construction replaces this infinite jump with a linear penalty. We augment the objective with a weighted sum of the constraint functions:

$$L(x, \lambda, \nu) = f_0(x) + \sum_{i=1}^m \lambda_i f_i(x) + \sum_{i=1}^p \nu_i h_i(x)$$

Here, $\lambda_i$ is the Lagrange multiplier. It acts as a "soft" penalty scaling the impact of the $i$-th inequality. Crucially, we do not assume convexity yet; this framework is universal.

The Dual Perspective

We define the Lagrange dual function $g(\lambda, \nu)$ as the infimum of the Lagrangian over $x$. A vital property is the Lower Bound Property: for any $\lambda \succeq 0$, $g(\lambda, \nu) \le p^*$. This allows us to bound the optimal value of problems that might otherwise be impossible to solve directly.

2. Case Study: Hybrid Vehicle Control

Imagine a vehicle balancing fuel consumption and battery life. The constraints are physical: power demand must be met at every moment.

Power Balance: $P_{\text{req}}(t) = p_{\text{eng}}(t) + p_{\text{mg}}(t) - p_{\text{br}}(t)$
Battery Dynamics: $E(t+1) = E(t) - p_{\text{mg}}(t) - \eta |p_{\text{mg}}(t)|$
Objective: Minimize $F_{\text{total}} = \sum_{t=1}^{T} F(p_{\text{eng}}(t))$

By applying the Lagrangian framework, battery capacity constraints are converted into shadow prices. The controller decides whether to burn fuel or use battery based on the current "cost" of energy (the multiplier) versus the fuel cost.

🎯 Core Principle: Duality & Feasibility

The lower bound property $p^* \in [g(\lambda, \nu), f_0(x)]$ is nontrivial only when $\lambda \succeq 0$ and $g(\lambda, \nu) > -\infty$. This relationship holds even in non-convex settings, though a "duality gap" may exist.

QUESTION 1

For an inequality constraint $f_i(x) \le 0$, what must be the sign of the corresponding Lagrange multiplier $\lambda_i$ for the dual function to provide a valid lower bound?

$\lambda_i \le 0$

$\lambda_i \ge 0$

$\lambda_i$ can be any real number

$\lambda_i = 0$

QUESTION 2

Which of the following statements about the Lagrange dual function $g(\lambda, \nu)$ is always true, regardless of the primal problem's convexity?

$g$ is a linear function.

$g$ is a convex function.

$g$ is a concave function.

$g$ is equal to $f_0(x)$ at all points.

QUESTION 3

In the KKT conditions, what does 'Complementary Slackness' imply for an inequality constraint?

$\lambda_i$ must always be zero.

The constraint must always be active ($f_i(x) = 0$).

The product $\lambda_i f_i(x)$ must be zero at the optimum.

$\lambda_i$ and $f_i(x)$ must both be strictly negative.

QUESTION 4

Consider Example 5.1: minimize $x^2 + 1$ subject to $(x-2)(x-4) \le 0$. What is the optimal value $p^*$?

$p^* = 1$

$p^* = 5$

$p^* = 17$

$p^* = 0$

QUESTION 5

In the hybrid vehicle example, if the Lagrange multiplier for the battery energy constraint is very high, what does this tell the controller?

Battery energy is 'cheap' and should be used freely.

The engine is very efficient and battery use is discouraged.

Battery energy is 'expensive' (a scarce resource), favoring fuel use.

The vehicle should stop and recharge immediately.